알고리즘 문제 [못 푼 문제] 백준 7576 정말 간단한 문제였지만 그 쉬운 한가지를 생각하지 못했다. 위 같은 경우 최댄 거리를 찾는 문제라 기본적으로 bfs를 사용하고 시작 지점이 둘 이상인 경우 단순히 시작 지점 둘다 큐에 넣어주면 그만인 것이다. 그리고 하나 더 프로그램을 종료싶은 경우 exit(0)를 사용하자.... 알고리즘 문제알고리즘 문제 [못 푼 문제] 백준 10989번 sys.stdin.readline()을 사용하여 input의 시간을 줄였다. 또한 입력 가능한 수의 개수가 10,000,000개 이고 최대 입력 가능한 수가 10,000이기 때문에 모든 수를 입력 받아 리스트로 만들어 sort하는 것 보다 크기 10,000인 리스트를 만들어 값을 1씩 올려주는게 더 낫다.... 알고리즘 문제알고리즘 문제 [못 푼 문제] 백준 2225번 생각을 깊게 못했다. d(n, k) = d(n, k-1) + d(n-1, k-1) + ... + d(1, k-1) + d(0, k-1) = d(n, k-1) + d(n-1, k)... 알고리즘 문제알고리즘 문제 [못 푼 문제] 백준 2011 전혀 이런 방식을 생각을 못했다. 당연히 앞에에 다 포함 된다는 말을 믿어야 한다.... 알고리즘 문제알고리즘 문제 [못 푼 문제] 백준 1406(스택/큐) 평범한 문제라서 insert와 del을 사용해서 리스트를 수정할 수 있지만 0.3초라는 제한된 시간 속에서 너무 많은 시간( O(N) )을 잡아먹게 된다. 그럼으로 커서의 왼쪽 리스트와 커서의 오른쪽 리스트를 만들어 시간이 상대적으로 적은 append와 pop을 이용하여 문제를 해결한다. ( O(1) )... 알고리즘 문제알고리즘 문제 [못 푼 문제] 백준 2004번 이번 문제는 단순 조합 계산을 하면 어려워진다. 마지막 끝자리가 0이 나오는 개수를 새보려고 하면 2와 5의 조합을 생각을 해야하는데 사실상 어렵다. 아래 코드를 보면 좀 이해가 될란지 모르겠다.... 알고리즘 문제알고리즘 문제 Algorithm/programmers/힙/level2/더 맵게 (with python) 리스트 scoville을 내림차순으로 정렬한다. scoville의 마지막 원소는 가장 안 매운 음식의 스코빌 지수가 된다. 두 음식을 섞었을 때 리스트에서 하나의 요소를 삭제해야 한다. 이때 만약 오름차순으로 정렬한다면 index 0의 요소를 삭제해야하는데 리스트에서 index 0 의 요소를 삭제하면 O(N)의 시간이 걸린다. 나름 시간 복잡도를 줄이기 위해서 내림차순으로 정렬했다.(ㅠㅠ) ... 알고리즘 문제힙programmersprogrammers Algorithm/programmers/2020 KAKAO BLIND RECRUITMENT /level2/문자열 압축 (with python) 압축 단위가 문자열 s의 길이의 1/2을 넘으면 압축이 안되기 때문에 압축 단위의 범위는 1 ~ len(s)//2이다. 이 범위를 모두 순회하여 모든 경우의 수를 구한다. (완전 탐색) <- 문자열 s의 최대 길이가 1000이어서 가능 압축 기준이 되는 문자열을 잡아서 압축이 가능한지 검사한다. unit 단위로 압축 기준이 되는 문자열을 잡는다. 바로 다음에 나오는 unit 단위의 문자열들과... 알고리즘 문제programmersprogrammers 프로그래머스 정수 내림차순 정렬 함수 solution은 정수 n을 매개변수로 입력받습니다. n의 각 자릿수를 큰것부터 작은 순으로 정렬한 새로운 정수를 리턴해주세요. 예를들어 n이 118372면 873211을 리턴하면 됩니다. n은 1이상 8000000000 이하인 자연수입니다. java의 sort와 Comparator를 사용하여 풀 수 있는 간단한 문제다. 근데 왜 정리해놨냐? Comparator를 사용함에 있어 제한 사... 알고리즘 문제알고리즘 문제 그래프와 인접행렬 예제 (ArrayList) 5개의 정점을 가지는 방향 그래프의 모든 경로의 가지 수를 출력하는 프로그램을 작성하는 문제가 있다. 이때 입력되는 예시는 입력받은 값을 그래프로 표현하면 위 그림과 같다. 총 가지수는 총 6개가 존재한다. 이를 DFS 알고리즘을 사용하여 풀어내보자. 경로 탐색에 인접 행렬은 정점의 수가 작을때는 괜찮지만 정점의 갯수가 10000개라면? 그때는 메모리의 크기가 10000씩 두개의 배열이 필요... 알고리즘 문제알고리즘 문제 [BOJ] 3190 뱀 - 삼성 SW 역량 테스트 기출 문제 요약 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다. 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다. 사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라. 접근방법 1. 뱀의 좌표 저장할 deque - 맨 앞값... 백준알고리즘 문제백준 ✔Algorithm/programmers/2017팁스다운/level2/짝지어 제거하기 (with python) 모든 문자열을 검사하는 직관적인 방식으로 문제를 풀었다. 문자열 내에서 2개 붙어있는 알파벳을 찾아서 ''(빈 문자열)로 대체한다. while문 밖으로 나왔을 때 만약 s가 빈 문자열이면 짝지어 제거하기가 성공적으로 이루어진 것이다. while문 밖으로 나왔을 때 s가 빈 문자열이 아니면 짝지어 제거하기가 실패한 것이다. 시간 복잡도가 O(n^2)라서 효율성 테스트에서 통과하지 못했다. 예)... 알고리즘 문제programmers스택programmers Algorithm/programmers/다이나믹 프로그래밍/level2/ 가장 큰 정사각형 찾기(with python) board의 최대 크기가 1000 x 1000이기 때문에 완전 탐색으로 했다가는 시간초과가 난다. 따라서 다이나믹 프로그래밍으로 문제를 푼다. 만약 주어진 board의 행이나 열의 길이가 2 미만인 경우에는 board에 1이 있는지 확인한다. 1이 있다면 가장 큰 정사각형의 크기는 1이므로 1을 리턴하고, 없다면 정사각형이 존재하지 않으므로 0을 리턴한다. board의 (1,1)부터 시작하여... 알고리즘 문제programmers다이나믹 프로그래밍programmers 이진 트리 순회(DFS) 이진 트리의 전위, 중위, 후위 순회를 직접 구현하세요. 전위 중위 후위 main 에서 만든 Node의 구조 Java의 class의 구조와 전위 중위 후위의 코드에서 Stack Frame의 개념을 알고 있다면 위 실행 결과를 이해하는데 도움이 될것이다.... 알고리즘 문제알고리즘 문제 Algorithm/programmers/level1/210612/5문제 (with python) 2021년 6월 12일 프로그래머스에서 푼 level1 5문제 모음집입니다. 문제 풀이에 대한 설명은 코드에 주석으로 표시하였습니다. len(s)가 홀수이면 (len(s)-1)//2 == len(s)//2인 특성을 이용하셨다. 내 코드는 arr에서 현재 문자와 이전 문자를 비교했는데 이 분들은 현재 문자는 arr에서, 이전 문자는 정답리스트의 끝(answer[-1])과 비교하는 방식으로 문제... pythonprogrammers알고리즘 문제programmers [BOJ] 1655 - 가운데를 말해요(Python)- 우선순위 큐(최대힙, 최소힙) 우선순위 큐(Priority Queue) 들어간 순서에 상관 없이 우선순위가 높은 데이터가 먼저 나오는 구조 우선순위를 따로 지정하지 않으면 값이 작을 수록 우선순위가 높다 힙을 통해 구현 -> heapq 모듈을 통해 구현할 수 있음 즉 완전이진트리 구조를 가지는 데, 대표적으로 최대힙, 최소힙 배열이나 연결리스트는 왜 X? -> 시간 복잡도 O(n) 최대힙 루트 노드가 가장 큰 값을 가지며... 백준알고리즘 문제백준 SWEA 9700. USB 꽂기의 미스터리 (with Python) 접근 방법 음.... 꽤나 고민을 했다. 나는 왜 이러케 멍청할까.. s1 구하기 1번 뒤집어서 성공해야 하기 때문에 처음에 옳바르지 않은 면으로 시도 (1-p) 그리고 1번 뒤집어서 성공 (q) (1-p) * q s2 구하기 2번 뒤집어서 성공해야 하기 때문에 처음에 옳바른 면으로 시도하지만 실패 (p * (1-q)) 뒤집어서 실패 (옳바른 면이 아니므로 무조건 실패) 뒤집어서 성공 (q)... 알고리즘 문제SWEASWEA 이진트리 레벨 탐색 (BFS) DFS는 실행시 가장 말단의 노드를 찍고 올라오면서 탐색하거나 가장 말단의 노드까지 탐색하며 내려가는 방법이였다면 BFS는 노드의 단계별 탐색을 하는 것을 의미한다. 우리가 코드에서 구현한 Node가 위 그림과 같은 트리 구조의 데이터를 가질 때 DFS의 경우 이러한 구조로 탐색하여 트리를 탐색한다고 생각하면 된다. BFS의 경우 위 두 그림처럼 단계별로 로 탐색하는 것을 의미한다. 우리는 ... 알고리즘 문제알고리즘 문제 [BOJ] 14499 주사위 굴리기 - 삼성SW역량테스트 기출 주사위 도면도를 가로부분, 세로부분 나눠서 생각 위, 아래를 공유함 동서남북 방향에 따라 주사위 전개도 업데이트 북쪽이면 세로부분 위로밀고 남쪽이면 아래로 밀고 동쪽이면 가로부분 오른쪽으로 밀고 서쪽이면 왼쪽으로 밀고 세로, 가로 부분 공유하는 위, 아래 부분 서로 같게 업데이트 지도가 0일 경우와 아닐 경우 나눠서 지도에 바닥값 복사 or 지도에 있는 값 주사위 바닥에 복사... 백준알고리즘 문제백준
[못 푼 문제] 백준 7576 정말 간단한 문제였지만 그 쉬운 한가지를 생각하지 못했다. 위 같은 경우 최댄 거리를 찾는 문제라 기본적으로 bfs를 사용하고 시작 지점이 둘 이상인 경우 단순히 시작 지점 둘다 큐에 넣어주면 그만인 것이다. 그리고 하나 더 프로그램을 종료싶은 경우 exit(0)를 사용하자.... 알고리즘 문제알고리즘 문제 [못 푼 문제] 백준 10989번 sys.stdin.readline()을 사용하여 input의 시간을 줄였다. 또한 입력 가능한 수의 개수가 10,000,000개 이고 최대 입력 가능한 수가 10,000이기 때문에 모든 수를 입력 받아 리스트로 만들어 sort하는 것 보다 크기 10,000인 리스트를 만들어 값을 1씩 올려주는게 더 낫다.... 알고리즘 문제알고리즘 문제 [못 푼 문제] 백준 2225번 생각을 깊게 못했다. d(n, k) = d(n, k-1) + d(n-1, k-1) + ... + d(1, k-1) + d(0, k-1) = d(n, k-1) + d(n-1, k)... 알고리즘 문제알고리즘 문제 [못 푼 문제] 백준 2011 전혀 이런 방식을 생각을 못했다. 당연히 앞에에 다 포함 된다는 말을 믿어야 한다.... 알고리즘 문제알고리즘 문제 [못 푼 문제] 백준 1406(스택/큐) 평범한 문제라서 insert와 del을 사용해서 리스트를 수정할 수 있지만 0.3초라는 제한된 시간 속에서 너무 많은 시간( O(N) )을 잡아먹게 된다. 그럼으로 커서의 왼쪽 리스트와 커서의 오른쪽 리스트를 만들어 시간이 상대적으로 적은 append와 pop을 이용하여 문제를 해결한다. ( O(1) )... 알고리즘 문제알고리즘 문제 [못 푼 문제] 백준 2004번 이번 문제는 단순 조합 계산을 하면 어려워진다. 마지막 끝자리가 0이 나오는 개수를 새보려고 하면 2와 5의 조합을 생각을 해야하는데 사실상 어렵다. 아래 코드를 보면 좀 이해가 될란지 모르겠다.... 알고리즘 문제알고리즘 문제 Algorithm/programmers/힙/level2/더 맵게 (with python) 리스트 scoville을 내림차순으로 정렬한다. scoville의 마지막 원소는 가장 안 매운 음식의 스코빌 지수가 된다. 두 음식을 섞었을 때 리스트에서 하나의 요소를 삭제해야 한다. 이때 만약 오름차순으로 정렬한다면 index 0의 요소를 삭제해야하는데 리스트에서 index 0 의 요소를 삭제하면 O(N)의 시간이 걸린다. 나름 시간 복잡도를 줄이기 위해서 내림차순으로 정렬했다.(ㅠㅠ) ... 알고리즘 문제힙programmersprogrammers Algorithm/programmers/2020 KAKAO BLIND RECRUITMENT /level2/문자열 압축 (with python) 압축 단위가 문자열 s의 길이의 1/2을 넘으면 압축이 안되기 때문에 압축 단위의 범위는 1 ~ len(s)//2이다. 이 범위를 모두 순회하여 모든 경우의 수를 구한다. (완전 탐색) <- 문자열 s의 최대 길이가 1000이어서 가능 압축 기준이 되는 문자열을 잡아서 압축이 가능한지 검사한다. unit 단위로 압축 기준이 되는 문자열을 잡는다. 바로 다음에 나오는 unit 단위의 문자열들과... 알고리즘 문제programmersprogrammers 프로그래머스 정수 내림차순 정렬 함수 solution은 정수 n을 매개변수로 입력받습니다. n의 각 자릿수를 큰것부터 작은 순으로 정렬한 새로운 정수를 리턴해주세요. 예를들어 n이 118372면 873211을 리턴하면 됩니다. n은 1이상 8000000000 이하인 자연수입니다. java의 sort와 Comparator를 사용하여 풀 수 있는 간단한 문제다. 근데 왜 정리해놨냐? Comparator를 사용함에 있어 제한 사... 알고리즘 문제알고리즘 문제 그래프와 인접행렬 예제 (ArrayList) 5개의 정점을 가지는 방향 그래프의 모든 경로의 가지 수를 출력하는 프로그램을 작성하는 문제가 있다. 이때 입력되는 예시는 입력받은 값을 그래프로 표현하면 위 그림과 같다. 총 가지수는 총 6개가 존재한다. 이를 DFS 알고리즘을 사용하여 풀어내보자. 경로 탐색에 인접 행렬은 정점의 수가 작을때는 괜찮지만 정점의 갯수가 10000개라면? 그때는 메모리의 크기가 10000씩 두개의 배열이 필요... 알고리즘 문제알고리즘 문제 [BOJ] 3190 뱀 - 삼성 SW 역량 테스트 기출 문제 요약 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다. 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다. 사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라. 접근방법 1. 뱀의 좌표 저장할 deque - 맨 앞값... 백준알고리즘 문제백준 ✔Algorithm/programmers/2017팁스다운/level2/짝지어 제거하기 (with python) 모든 문자열을 검사하는 직관적인 방식으로 문제를 풀었다. 문자열 내에서 2개 붙어있는 알파벳을 찾아서 ''(빈 문자열)로 대체한다. while문 밖으로 나왔을 때 만약 s가 빈 문자열이면 짝지어 제거하기가 성공적으로 이루어진 것이다. while문 밖으로 나왔을 때 s가 빈 문자열이 아니면 짝지어 제거하기가 실패한 것이다. 시간 복잡도가 O(n^2)라서 효율성 테스트에서 통과하지 못했다. 예)... 알고리즘 문제programmers스택programmers Algorithm/programmers/다이나믹 프로그래밍/level2/ 가장 큰 정사각형 찾기(with python) board의 최대 크기가 1000 x 1000이기 때문에 완전 탐색으로 했다가는 시간초과가 난다. 따라서 다이나믹 프로그래밍으로 문제를 푼다. 만약 주어진 board의 행이나 열의 길이가 2 미만인 경우에는 board에 1이 있는지 확인한다. 1이 있다면 가장 큰 정사각형의 크기는 1이므로 1을 리턴하고, 없다면 정사각형이 존재하지 않으므로 0을 리턴한다. board의 (1,1)부터 시작하여... 알고리즘 문제programmers다이나믹 프로그래밍programmers 이진 트리 순회(DFS) 이진 트리의 전위, 중위, 후위 순회를 직접 구현하세요. 전위 중위 후위 main 에서 만든 Node의 구조 Java의 class의 구조와 전위 중위 후위의 코드에서 Stack Frame의 개념을 알고 있다면 위 실행 결과를 이해하는데 도움이 될것이다.... 알고리즘 문제알고리즘 문제 Algorithm/programmers/level1/210612/5문제 (with python) 2021년 6월 12일 프로그래머스에서 푼 level1 5문제 모음집입니다. 문제 풀이에 대한 설명은 코드에 주석으로 표시하였습니다. len(s)가 홀수이면 (len(s)-1)//2 == len(s)//2인 특성을 이용하셨다. 내 코드는 arr에서 현재 문자와 이전 문자를 비교했는데 이 분들은 현재 문자는 arr에서, 이전 문자는 정답리스트의 끝(answer[-1])과 비교하는 방식으로 문제... pythonprogrammers알고리즘 문제programmers [BOJ] 1655 - 가운데를 말해요(Python)- 우선순위 큐(최대힙, 최소힙) 우선순위 큐(Priority Queue) 들어간 순서에 상관 없이 우선순위가 높은 데이터가 먼저 나오는 구조 우선순위를 따로 지정하지 않으면 값이 작을 수록 우선순위가 높다 힙을 통해 구현 -> heapq 모듈을 통해 구현할 수 있음 즉 완전이진트리 구조를 가지는 데, 대표적으로 최대힙, 최소힙 배열이나 연결리스트는 왜 X? -> 시간 복잡도 O(n) 최대힙 루트 노드가 가장 큰 값을 가지며... 백준알고리즘 문제백준 SWEA 9700. USB 꽂기의 미스터리 (with Python) 접근 방법 음.... 꽤나 고민을 했다. 나는 왜 이러케 멍청할까.. s1 구하기 1번 뒤집어서 성공해야 하기 때문에 처음에 옳바르지 않은 면으로 시도 (1-p) 그리고 1번 뒤집어서 성공 (q) (1-p) * q s2 구하기 2번 뒤집어서 성공해야 하기 때문에 처음에 옳바른 면으로 시도하지만 실패 (p * (1-q)) 뒤집어서 실패 (옳바른 면이 아니므로 무조건 실패) 뒤집어서 성공 (q)... 알고리즘 문제SWEASWEA 이진트리 레벨 탐색 (BFS) DFS는 실행시 가장 말단의 노드를 찍고 올라오면서 탐색하거나 가장 말단의 노드까지 탐색하며 내려가는 방법이였다면 BFS는 노드의 단계별 탐색을 하는 것을 의미한다. 우리가 코드에서 구현한 Node가 위 그림과 같은 트리 구조의 데이터를 가질 때 DFS의 경우 이러한 구조로 탐색하여 트리를 탐색한다고 생각하면 된다. BFS의 경우 위 두 그림처럼 단계별로 로 탐색하는 것을 의미한다. 우리는 ... 알고리즘 문제알고리즘 문제 [BOJ] 14499 주사위 굴리기 - 삼성SW역량테스트 기출 주사위 도면도를 가로부분, 세로부분 나눠서 생각 위, 아래를 공유함 동서남북 방향에 따라 주사위 전개도 업데이트 북쪽이면 세로부분 위로밀고 남쪽이면 아래로 밀고 동쪽이면 가로부분 오른쪽으로 밀고 서쪽이면 왼쪽으로 밀고 세로, 가로 부분 공유하는 위, 아래 부분 서로 같게 업데이트 지도가 0일 경우와 아닐 경우 나눠서 지도에 바닥값 복사 or 지도에 있는 값 주사위 바닥에 복사... 백준알고리즘 문제백준